#ifndef STX_ALGORITHM_INCLUDES_HPP
#define STX_ALGORITHM_INCLUDES_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class Compare, class InputIterator1, class InputIterator2>
inline bool
includes_impl(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    Compare comp)
{
    for (; first2 != last2; ++first1) {
        if (first1 == last1 || comp(*first2, *first1)) {
            return false;
        }
        if (!comp(*first1, *first2)) {
            ++first2;
        }
    }
    return true;
}

template <class InputIterator1, class InputIterator2, class Compare>
inline bool
includes(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return includes_impl<comp_ref>(first1, last1, first2, last2, comp);
}

template <class InputIterator1, class InputIterator2>
inline bool
includes(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2)
{
    return stx::includes(
        first1,
        last1,
        first2,
        last2,
        stx::less<typename std::iterator_traits<InputIterator1>::value_type,
                  typename std::iterator_traits<InputIterator2>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_INCLUDES_HPP
